package week8;

/**
 *
 *
 * 200. 岛屿数量
 * https://leetcode-cn.com/problems/number-of-islands/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：8 ms, 在所有 Java 提交中击败了8.05% 的用户
 * 内存消耗：46.5 MB, 在所有 Java 提交中击败了58.90% 的用户
 * 通过测试用例：49 / 49
 * 炫耀一下:
 *
 *
 */
public class Week8NumberOfIslands {

    public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0) {
            return 0;
        }
        int rowLength = grid.length;
        int columnLength = grid[0].length;
        UnionFind unionFind = new UnionFind(grid);
        for(int row = 0; row < rowLength; row++) {
            for(int column = 0; column < columnLength; column++) {
                if(grid[row][column] == '1') {
                    grid[row][column] = '0';
                    if(row - 1 >= 0 && grid[row - 1][column] == '1') {
                        unionFind.union(row * columnLength + column, (row - 1) * columnLength + column);
                    }
                    if(row + 1 < rowLength && grid[row + 1][column] == '1') {
                        unionFind.union(row * columnLength + column, (row + 1) * columnLength + column);
                    }
                    if(column - 1 >= 0 && grid[row][column - 1] == '1') {
                        unionFind.union(row * columnLength + column, row * columnLength + column - 1);
                    }
                    if(column + 1 < columnLength && grid[row][column + 1] == '1') {
                        unionFind.union(row * columnLength + column, row * columnLength + column + 1);
                    }
                }
            }
        }

        return unionFind.getCount();
    }

    class UnionFind {
        int count;
        int[] parent;
        int[] rank;

        public UnionFind(char[][] grid) {
            count = 0;
            int rowLength = grid.length;
            int columnLength = grid[0].length;
            parent = new int[rowLength * columnLength];
            rank = new int[rowLength * columnLength];
            for(int column = 0; column < rowLength; column++) {
                for(int row = 0; row < columnLength; row++) {
                    if(grid[column][row] == '1') {
                        parent[column * columnLength + row ] = column * columnLength + row;
                        count++;
                    }
                    rank[column * columnLength + row] = 0;
                }
            }
        }

        public int find(int index) {
            if(parent[index] != index) {
                parent[index] = find(parent[index]);
            }

            return parent[index];
        }

        public void union(int row, int column) {
            int findColumn = find(row);
            int findRow = find(column);
            if(findColumn != findRow) {
                if(rank[findColumn] > rank[findRow]) {
                    parent[findRow] = findColumn;
                } else if(rank[findColumn] < rank[findRow]) {
                    parent[findColumn] = findRow;
                } else {
                    parent[findRow] = findColumn;
                    rank[findColumn] += 1;
                }
                count--;
            }
        }

        public int getCount() {
            return count;
        }
    }
}
